#pragma once
#include <iostream>
#include <assert.h>

using namespace std;

class ListNode
{
public:
	int data;
	ListNode* next;
	ListNode(int x)
	{
		data = x;
		next = nullptr;
	}
};

class List
{
public:
	List()
	{
		head = nullptr;
	}
	void Print()
	{
		ListNode* cur = head;
		while (cur)
		{
			cout << cur->data << " ";
			cur = cur->next;
		}
		cout << endl;
	}
	ListNode* CreateNode(int x)
	{
		ListNode* newnode = new ListNode(x);
		return newnode;
	}
	void Push_back(int x)
	{
		ListNode* newnode = CreateNode(x);
		ListNode* tail = head;
		if (tail == nullptr) head = tail = newnode;
		else
		{
			while (tail->next)
			{
				tail = tail->next;
			}
			tail->next = newnode;
		}
	}
	void Push_front(int x)
	{
		ListNode* newnode = CreateNode(x);
		newnode->next = head;
		head = newnode;
	}
	void Pop_back()
	{
		assert(head);
		if (head->next == nullptr)
		{
			Delete();
		}
		ListNode* tail = head;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		delete tail->next;
		tail->next = nullptr;
	}
	void Delete()
	{
		ListNode* cur = head;
		while (cur)
		{
			ListNode* next = cur->next;
			delete cur;
			cur = next;
		}
		head = nullptr;
	}
	void Pop_front()
	{
		assert(head);
		if (head->next == nullptr)
		{
			Delete();
		}
		ListNode* first = head->next;
		delete head;
		head = first;
	}
	ListNode* Find(int x)
	{
		ListNode* cur = head;
		while (cur)
		{
			if (cur->data == x)
			{
				return cur;
			}
			cur = cur->next;
		}
		return nullptr;
	}
	void InsertPos(ListNode* pos, int x)
	{
		assert(pos);
		ListNode* newnode = CreateNode(x);
		ListNode* prev = head;
		ListNode* cur = prev->next;
		if (pos == head) Push_front(x);
		while (cur)
		{
			if (pos == cur)
			{
				newnode->next = cur;
				prev->next = newnode;
				return;//
			}
			prev = prev->next;
			cur = prev->next;
		}
	}
	void ErasePos(ListNode* pos)
	{
		assert(pos);
		if (pos == head) Pop_front();
		ListNode* prev = head;
		ListNode* cur = prev->next;
		while (cur)
		{
			if (cur == pos)
			{
				ListNode* next = cur->next;
				delete cur;
				prev->next = next;
				return;
			}
			prev = prev->next;
			cur = prev->next;
		}

	}

	~List()
	{
		Delete();
	}

private:
	ListNode* head;
};